#pragma once
#include <iostream>

namespace K_simulation {
	template<class K>
	struct BSTreeNode {
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;

		BSTreeNode(const K& key)
			: _left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}
	};

	template<class K>
	class BSTree {
	private:
		typedef BSTreeNode<K> Node;
		Node* _root;

	public:
		BSTree()
			: _root(nullptr)
		{}

		BSTree(const K& key)
			: _root(new Node(key))
		{}

		BSTree(const BSTree<K>& tree)
			: _root(copy(tree._root)) //封装是对其他类隐藏private对象，相同类可以互相访问private对象
		{}

		BSTree<K>& operator=(const BSTree<K>& tree)
		{
			if (this != &tree)
			{
				BSTree<K> temp(tree);
				std::swap(_root, temp._root);
			}

			return *this;
		}

		~BSTree()
		{
			destroy(_root);
			_root = nullptr;
		}

		bool insert(const K& key)
		{
			//当根节点为空时 直接将key构造的节点作根节点
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}

			//当根节点不为空时要找到合适的位置
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (key > cur->_key) //如果传入的key比当前节点的_key要大，说明key要插入当前节点的右子树，因此cur向右子树走
				{
					parent = cur; //每次向左、右子树走时都要更改一下parent的位置
					cur = cur->_right;
				}
				else if (key < cur->_key) //与if相反
				{
					parent = cur;
					cur = cur->_left;
				}
				else // key == cur->_key 因为二叉搜索树各个节点的key值不能相同，所以发现传入的key与树上的_key重复时就返回false，说明插入失败
				{
					return false;
				}
			}

			//走出while循环标明要不满足if要不满足else if且cur == nullptr，需要对其进行判断是满足哪种情况才能判明key是插入parent的左子树还是右子树
			cur = new Node(key);
			key < parent->_key 
				? parent->_left = cur 
				: parent->_right = cur;

			return true;
		}

		void inOrder() const
		{
			_inOrder(_root);
			std::cout << std::endl;
		}

		bool find(const K& key) const
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key == key)
				{
					return true;
				}
				else if (key > cur->_key)
				{
					cur = cur->_right;
				}
				else
				{
					cur = cur->_left;
				}
			}

			//没找到或者_root == nullptr都会到这里返回false
			return false;
		}

		bool remove(const K& key)
		{
			//被删除的节点有4种情况：
			//1、没有孩子 2、没有左孩子 3、没有右孩子 4、左右孩子都有
			//其中2、3情况处理的方式相同，1情况可以与2、3情况一起处理，比如没有左孩子但不一定会有右孩子，此时就是左右孩子都没有即没有孩子
			
			//先找到要被删除的节点
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur) //cur != null
			{
				if (key > _root->_key)
				{
					cur = cur->_right;
				}
				else if (key < _root->_key)
				{
					cur = cur->_left;
				}
				else //找到了要删除的节点
				{
					//如果要被删除的节点没有左孩子，能把没有孩子的情况一起处理了
					if (cur->_left == nullptr)
					{
						if (cur == _root) //要删除的节点是根节点，此时parent == nullptr
						{
							_root = cur->_right;
						}
						else //要删除的节点不是根节点
						{
							//判断要删除的节点是其父节点的左孩子还是右孩子，并做出不同的处理
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
					}
					else if (cur->_right == nullptr) //没有右孩子
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
					}
					else //有两个孩子
					{
						//要以cur作为根，去找cur左子树的最大值（最右节点）或cur右子树的最小值（最左节点）
						//我们可以将目标节点与cur的key交换，然后删除目标节点就行了。因为目标节点一定会没有左孩子（或右孩子），这样就能与情况2、3一样处理了

						//找右子树的最左节点
						Node* parent = cur;
						Node* rightMin = cur->_right; //右子树的最左(小)节点

						while (rightMin->_left) //当rightMin为nullptr时停下，此时rightMin就满足条件
						{
							parent = rightMin;
							rightMin = rightMin->_left;
						}

						cur->_key = rightMin->_key; //用覆盖代替交换，反正rightMin都要被删除，那么它具体的值就无所谓了

						if (rightMin == parent->_left)
						{
							parent->_left = rightMin->_right;
						}
						else
						{
							parent->_right = rightMin->_right;
						}

						//将rightMin赋值给cur，方便一起处理
						cur = rightMin;
					}

					delete cur;
					return true;
				}
			}

			return false;
		}

		bool insertR(const K& key)
		{
			return _insertRecursionVer(_root, key);
		}

		bool removeR(const K& key)
		{
			return _removeRecursionVer(_root, key);
		}

		bool findR(const K& key) const
		{
			return _findRecursionVer(_root, key);
		}

	private:
		void _inOrder(Node* root) const
		{
			if (root == nullptr) return;

			_inOrder(root->_left);
			std::cout << root->_key << " ";
			_inOrder(root->_right);
		}

		void destroy(Node* root)
		{
			if (root == nullptr) return;

			//采用后续遍历删除一棵二叉树
			destroy(root->_left);
			destroy(root->_right);
			delete root;
		}

		/*
		* 采用前序遍历拷贝一棵二叉树
		* @para root 要拷贝的二叉树的根节点
		* @return 拷贝出来的新二叉树的根节点
		*/
		Node* copy(Node* root) const
		{
			if (root == nullptr) return nullptr;

			Node* newRoot = new Node(root->_key);
			newRoot->_left = copy(root->_left);
			newRoot->_right = copy(root->_right);

			return newRoot;
		}

		bool _insertRecursionVer(Node*& root, const K& key) //这里要传入指针的引用来对指针进行修改，或者传二级指针也行
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}

			if (key > root->_key)
			{
				return _insertRecursionVer(root->_right, key);
			}
			else if (key < root->_key)
			{
				return _insertRecursionVer(root->_left, key);
			}
			else
			{
				return false;
			}
		}

		bool _findRecursionVer(Node* root, const K& key) const
		{
			if (root == nullptr) return false;

			if (key > root->_key) 
				return _findRecursionVer(root->_right, key);
			else if (key < root->_key) 
				return _findRecursionVer(root->_left, key);
			else 
				return true;
		}

		bool _removeRecursionVer(Node*& root, const K& key)
		{
			if (root == nullptr) return false;

			if (key > root->_key)
			{
				return _removeRecursionVer(root->_right, key);
			}
			else if (key < root->_key)
			{
				return _removeRecursionVer(root->_left, key);
			}
			else //找到了
			{
				Node* del = root;
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* rightMin = root->_right;
					while (rightMin->_left)
						rightMin = rightMin->_left;

					std::swap(root->_key, rightMin->_key);

					//转化成到子树中去删除节点，最后一定会是（root->_left == nullptr）或（root->_right == nullptr）其中一种
					return _removeRecursionVer(root->_right, key);
				}

				delete del;
				return true;
			}
		}
	};
}

namespace KV_simulation {
	template<class K, class V>
	struct BSTreeNode {
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;

		BSTreeNode(const K& key, const V& value)
			: _left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}
	};

	template<class K, class V>
	class BSTree {
	private:
		typedef BSTreeNode<K, V> Node;
		Node* _root;

	public:
		BSTree()
			: _root(nullptr)
		{}

		bool insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* cur = _root;
			Node* parent = nullptr;

			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(key, value);
			key < parent->_key
				? parent->_left = cur
				: parent->_right = cur;

			return true;
		}

		const Node*& find(const K& key) const
		{
			Node* cur = _root;

			while (cur)
			{
				if (key > cur->_key)
					cur = cur->_right;
				else if (key < cur->_key)
					cur = cur->_left;
				else
					return cur;
			}

			return nullptr;
		}

		void inOrder() const
		{
			_inOrder(_root);
		}

	private:
		void _inOrder(Node* root) const
		{
			if (root == nullptr) return;

			_inOrder(root->_left);
			std::cout << root->_key << ":" << root->_value << std::endl;
			_inOrder(root->_right);
		}
	};
}